https://leetcode.cn/problems/a7VOhD/description/
//class Solution {
//public:
//    int countSubstrings(string s)
//    {
//        int n = s.size();
//
//        vector<vector<bool>> dp(n, vector<bool>(n));
//        int ret = 0;
//        for (int i = n - 1; i >= 0; i--)
//        {
//            for (int j = i; j < n; j++)
//            {
//                if (s[i] == s[j])
//                {
//                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
//                }
//                if (dp[i][j]) ret++;
//            }
//        }
//        return ret;
//    }
//};

https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/
//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums)
//    {
//        int n = nums.size();
//        unordered_map<long long, vector<int>> hash;
//        for (int i = 0; i < n; i++) hash[nums[i]].push_back(i);
//
//        vector<vector<int>> dp(n, vector<int>(n));
//
//        int sum = 0;
//        for (int j = 2; j < n; j++)
//        {
//            for (int i = 1; i < j; i++)
//            {
//                long long  a = (long long)2 * nums[i] - nums[j];
//                if (hash.count(a))
//                {
//                    for (auto k : hash[a])
//                    {
//                        if (k < i)         dp[i][j] += dp[k][i] + 1;
//                    }
//                }
//                sum += dp[i][j];
//            }
//        }
//        return sum;
//
//    }
//};